CF167E Wizards and Bets

首先,我们将所有源点与汇点筛出来,然后从每一个源点dfs求出它到各汇点的路径数,题目中保证源点与汇点数量相同,我们记为cntcnt
那么,我们可以得到一个cntcntcnt * cnt的矩阵。

先考虑路径不相交的情况(似乎大家思路都是这样),题目求的是一个排列的逆序对数,记为τ(σ)\tau(\sigma)。那么,题目等价于求:

(1)τ(σ)f i σi\sum(-1)^{\tau(\sigma)}*\prod{f_{~i~\sigma_i}}

其中,fi σif_{i~\sigma_i}表示i号源点走到σi\sigma_i号汇点的路径数。

结合上文,不难很难想到行列式。然后,你会发现,矩阵的行列式就是答案。


然后,我们考虑路径相交的情况,发现答案不变。

graph _1_.png

显然,(14),(25)(1 \to 4),(2 \to 5)路径相交了

我们考虑交换4,54,5位置

graph.png

还是相交的

这虽然不能解决我们的问题,但我们发现,经过交换后,汇点序列的逆序对数奇偶性变了,也就是矩阵行列式的其中一项变号。同时,路径数却没有变。所以,两种情况相互抵消了!!!

所以,路径相交并不会影响答案,直接算行列式即可。


本代码由@Krain大佬修改,可能神似请见谅。

同时,求矩阵行列式时消元必须在整数范围内运算,需要用到辗转相除的高斯消元,此处不再赘述。

#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAXN = 600;
int n , m , x , y , p , cnt;
int Ind[ MAXN + 5 ] , Outd[ MAXN + 5 ];
int s[ MAXN + 5 ][ MAXN + 5 ];
int tmp[ MAXN + 5 ] , f[ MAXN + 5 ][ MAXN + 5 ];
vector< int > Graph[ MAXN + 5 ];
vector< int > S , T;

int Mo( long long x ) {
	return ( x % p + p ) % p;
}
int Gauss( ) {
	int Sign = 1;
    for( int i = 1 ; i <= cnt ; i ++ ) {
    	for( int j = i + 1 ; j <= cnt ; j ++ ) {
    		int A = f[ i ][ i ] , B = f[ j ][ i ];
    		while( B ) {
    			int t = A / B; A %= B; swap( A , B );
    			for( int k = i ; k <= n ; k ++ )
    				f[ i ][ k ] = Mo( 1ll * f[ i ][ k ] - 1ll * t * f[ j ][ k ] );
    			
    			swap( f[ i ] , f[ j ] );
    			Sign *= -1;
			}
		}
    	if( !f[ i ][ i ] ) return 0;
    }
    int Ans = 1;
    for( int i = 1 ; i <= cnt ; i ++ )
        Ans = ( 1ll * Ans * f[ i ][ i ] ) % p;
    return Mo( 1ll * Ans * Sign );
}

bool vis[ MAXN + 5 ];
void dfs( int u ) {
	vis[ u ] = 1;
    if( !Outd[ u ] ) s[ u ][ u ] = 1;
    for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
        int v = Graph[ u ][ i ];
        if( !vis[ v ] ) dfs( v );
        for( int j = 0 ; j < T.size() ; j ++ )
        	s[ u ][ T[ j ] ] = Mo( 1ll * s[ u ][ T[ j ] ] + s[ v ][ T[ j ] ] );
    } 
}
int main( ) {
    scanf("%d %d %d",&n,&m,&p);
    for( int i = 1 ; i <= m ; i ++ ) {
        scanf("%d %d",&x,&y);
        Graph[ x ].push_back( y );
        Outd[ x ] ++ , Ind[ y ] ++;
    }
    for( int i = 1 ; i <= n ; i ++ ) {
    	if( !Ind[ i ] )
    		S.push_back( i );
    	if( !Outd[ i ] )
    		T.push_back( i );
	}
    for( int i = 1 ; i <= n ; i ++ )
        if( !Ind[ i ] ) dfs( i );
    
    for( int i = 0 ; i < S.size() ; i ++ )
    	for( int j = 0 ; j < T.size() ; j ++ )
    		f[ i + 1 ][ j + 1 ] = s[ S[ i ] ][ T[ j ] ];
    cnt = S.size();
    printf("%d",Gauss( ));
    return 0;
}